﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DistributedGraph.EIGStop
{
    /// <summary>
    /// Bildet einen Knoten eines EIGTrees ab.
    /// </summary>
    public struct TreeNode
    {
        private List<TreeNode> children;
        private int[] label;
        private int value;
        private bool isNull;
        /// <summary>
        /// Gibt alle Kindknoten an.
        /// </summary>
        public List<TreeNode> Children { get { return children; } }

        /// <summary>
        /// Gibt den Kennzeichner an.
        /// </summary>
        public int[] Label { get { return label; } }

        /// <summary>
        /// Gibt den Wert an.
        /// </summary>
        public int Value
        {
            get
            {
                if (isNull) throw new Exception("Dieser TreeNode ist null.");
                return value;
            }
            internal set { this.value = value; }
        }
        /// <summary>
        /// Gibt an ob der Knoten Null ist. (Im Fehlerfall true)
        /// </summary>
        public bool IsNull { get { return isNull; } }
        /// <summary>
        /// Gibt die Ebene des Knotens an.
        /// </summary>
        public int Level { get { return Label.Length; } }

        /// <summary>
        /// Initialisiert die Struktur mit einem Wert.
        /// </summary>
        /// <param name="label">Die Kennzeichnung.</param>
        /// <param name="value">Der Wert.</param>
        public TreeNode(int[] label, int value)
        {
            this.children = new List<TreeNode>();
            this.label = label;
            this.value = value;
            this.isNull = false;
        }

        /// <summary>
        /// Initialisiert die Struktur als Null.
        /// </summary>
        /// <param name="label">Die Kennzeichnung.</param>
        public TreeNode(int[] label)
        {
            this.children = new List<TreeNode>();
            this.label = label;
            this.value = 0;
            this.isNull = true;
        }

        /// <summary>
        /// Gibt den Kindknoten zurück an dem der angegebene Knoten eingeordnet werden soll
        /// </summary>
        /// <param name="newChild"></param>
        /// <returns></returns>
        public TreeNode GetMatchingLeave(TreeNode newChild)
        {
            if (Level >= newChild.Level) throw new Exception("Das Kind muss sich auf der folgenden Ebene befinden.");
            int i = 0;
            while (i < children.Count && children[i].Label[Level] != newChild.Label[Level]) i++;
            return i < children.Count ? children[i].GetMatchingLeave(newChild) : this;
        }

        /// <summary>
        /// Gibt alle Blätter des Baums zurück.
        /// </summary>
        /// <returns>Eine Liste der Blätter.</returns>
        public List<TreeNode> GetLeaves()
        {
            List<TreeNode> nodes = new List<TreeNode>();
            if (children.Count == 0) nodes.Add(this);
            else foreach (TreeNode child in children) nodes.AddRange(child.GetLeaves());
            return nodes;
        }

        /// <summary>
        /// Gibt eine Zeichenkettenrepräsentation des Baumknotens zurück.
        /// </summary>
        /// <returns>Eine Zeichenkette.</returns>
        public override string ToString()
        {
            string text = "";
            foreach (int i in Label) text += i.ToString() + " ";
            text += "= " + (isNull ? "null" : Value.ToString());
            return text;
        }

        /// <summary>
        /// Erstellt einen Clon des Knotens und aller Unterknoten.
        /// </summary>
        /// <returns></returns>
        public TreeNode Clone()
        {
            TreeNode newNode = isNull ? new TreeNode(label) : new TreeNode(label, value);
            foreach (TreeNode tn in children) newNode.Children.Add(tn.Clone());
            return newNode;
        }

        /// <summary>
        /// Erweitert den Knoten und gibt eine Kopie zurück, wobei die Kinder entfernt werden.
        /// </summary>
        /// <param name="id">Die neue Id.</param>
        /// <returns>Der erweiterte Knoten.</returns>
        public TreeNode Extend(int id)
        {
            List<int> ll = label.ToList();
            ll.Add(id);
            return isNull ? new TreeNode(ll.ToArray()) : new TreeNode(ll.ToArray(), value);
        }

        /// <summary>
        /// Ermittelt die Anzahl der Elemente für einen EIGBaum T(n,f)
        /// (Siehe auch Gegenüberstellung der Algorithmen)
        /// </summary>
        /// <param name="n">Anzahl der Knoten im Algorithmus</param>
        /// <param name="f">Anzahl der fehlerhaften Knoten im Algorithmus</param>
        /// <returns>Anzahl der Knoten im Baum.</returns>
        public static int CalculateTreeElementCount(int n, int f)
        {
            int summe = 0;
            for (int k = 0; k <= f + 1; k++) summe += M(n, 0, k);
            return summe;
        }

        /// <summary>
        /// Ermittelt die Anzahl der Elemente für eine Teilebene.
        /// </summary>
        /// <param name="n">Knotenanzahl im Algorithmus (konstant)</param>
        /// <param name="i">Startebene</param>
        /// <param name="k">Endebene</param>
        /// <returns>Anzahl der Elemente.</returns>
        private static int M(int n, int i, int k)
        {
            return i < k ? (n - i) * M(n, i + 1, k) : 1;
        }
    }
}
